#pragma once
#include<time.h>
#include<iostream>
#include"Graph_Functions.h"
#include<algorithm>
#include"Tests.h"
#include<queue>
#include <stdexcept>

vector<bool> check_path(int first_vertex, const unique_ptr<IGraph> & graph)
{
	vector<bool>used(graph->get_number_of_vertice(), false);
	queue<int> QUEUE;
	QUEUE.push(first_vertex);
	used[first_vertex] = true;
	while(!QUEUE.empty())
	{
		int vertex = QUEUE.front();
		QUEUE.pop();
		vector<int> adjacents = graph->get_list_adjacents(vertex);
		for (int cur = 0; cur < adjacents.size(); ++cur)
		{
			int to = adjacents[cur];
			if (used[to]) continue;
			used[to] = true;
			QUEUE.push(to);
		}
	}
	return used;
}

void Mega_Tarjan_Check()
{
	for(int i = 1; i<201; ++i, cerr << i <<"\n")
	{
		for(int j = 1; j <= 19; ++j)
		{
			double pass = j/100.0;
			vector<pair<int, int> > graph = random_graph(i, pass);
			auto experimental_graph = compact_graph(i, graph);
		
			vector<int> components = component(experimental_graph);

			vector<vector<bool> > Transitive;
			for(int cur = 0; cur < i; ++cur)
				Transitive.push_back(check_path(cur, experimental_graph));
		
			for(int first_vertex = 0; first_vertex < experimental_graph->get_number_of_vertice(); ++first_vertex)
				for(int second_vertex = 0; second_vertex < experimental_graph->get_number_of_vertice(); ++second_vertex)
				{
					bool path = (Transitive[first_vertex][second_vertex] && Transitive[second_vertex][first_vertex]);
					bool achievity = (components[first_vertex] == components[second_vertex]);
					if (path != achievity) 
					{
						throw std::logic_error("");
					}
				}
		}
	}
}